package leetcode_top;

import org.junit.*;
import linked.*;

public class Ex143 {

    class Solution1 {
        public void reorderList(ListNode head) {
            if (head == null || head.next == null)
                return;
            ListNode p = head, q = head, tmp = null, h1 = p, h2 = q;
            boolean lastQ = false;
            while (p != null && p.next != null) {
                tmp = q;
                p  = p.next.next;
                q = q.next;
            }
            tmp.next = null;
            h2 = reverse(q);
            System.out.println(h1);
            System.out.println(h2);
            head = h1;
            while (h1 != null && h2 != null) {
                tmp = h1.next;
                h1.next = h2;
                p = h2.next;
                h2.next = tmp;
                h1 = tmp;
                h2 = p;
            }
            if (h2 != null) {
                p = head;
                while (p.next != null)
                    p = p.next;
                p.next = h2;
            }
            return;
        }

        public ListNode reverse(ListNode p) {
            ListNode pre = null, post = p, tmp;
            while (post != null) {
                tmp = post.next;
                post.next = pre;
                pre = post;
                post = tmp;
            }
            return pre;
        }
    }

    class Solution {

        //后序思想：假设头尾中间的链表已经处理好了,那么只需要将头变成中间链表的尾部，将中间链表头部的上一个节点变成现在链表的尾结点即可

            /* 
                      难点：
                      1）跳出条件：
                      当中间链表只有1~2个节点时，当返回null；
                      因为tail和head中间没有链表
                      2）需要返回中点链表的尾结点，使得无需遍历获取尾结点
                      中间状态： head -> mid -> tail => head.next = mid.head; mid.tail.next = tail;
                      我们需要保证在o(1)时间内得到mid.head和mid.tail
                      3）循环依托：
                      len，当len降低到1或者2时，递归出栈
                      4) 中间元素需要最后与外界脱离关系，防止出现环
                  */
                  public void reorderList(ListNode head) {
                      int len = 0;
                      ListNode h = head;
                      while (h != null) {
                          h = h.next;
                          len++;
                      } 
                      help(head, len);
                  }
          
                  public ListNode help(ListNode head, int len) {
                      if (len == 1) {
                          ListNode tail = head.next;
                          head.next = null;
                          return tail; //就是当前那段链表之右的那个节点
                      }
                      if (len == 2) {
                          ListNode tail = head.next.next;
                          head.next.next = null;
                          return tail; //就是当前那段链表之右的那个节点
                      }
                      ListNode t = help(head.next, len - 2),
                      h = head.next,
                      tail = t.next;
                      t.next = null;
                      t.next = h; //尾结点拿到头结点的后一个位置=> 1->(2 -> 3) -> 4 => 1 -> 4 -> 2 -> 3
                      head.next = t;
                      return tail; //就是当前那段链表之右的那个节点
                  }
              }

    @Test
    public void test() {
        Solution s = new Solution();
        ListNode h1 = ListNode.newListNodeFromArray(new int[]{1,2,3,4,5});
        s.reorderList(h1);
        System.out.println(h1);
    }
}
